Read the original article here.

---

Dataflow Programming: A Lost Innovation Ahead of Its Time

Introduction to Dataflow Programming

In the realm of computer programming paradigms, dataflow programming stands out as a unique approach that contrasts sharply with the more traditional, command-centric styles. Instead of focusing on a sequence of instructions, dataflow programming centers around the flow of data between operations.

Dataflow Programming: A programming paradigm that models a program as a directed graph where nodes represent operations and edges represent the flow of data between these operations. Computation is driven by the availability of data.

Imagine a program not as a recipe with step-by-step instructions, but as a network of interconnected processing units. Each unit performs a specific task, and as soon as it has the necessary input data, it springs into action. This is the essence of dataflow programming.

Dataflow programming shares some conceptual ground with functional programming languages, particularly in its emphasis on operations as functions and the immutability of data. It was initially conceived as a way to bring functional programming principles to languages better suited for numerical computations, especially in the context of parallel processing.

Sometimes, the term "datastream programming" is used synonymously, or to further emphasize the continuous nature of data flow, especially to differentiate it from dataflow computing or architecture, which can refer to specific hardware designs built around dataflow principles.

Dataflow programming's origins can be traced back to the 1960s, pioneered by Jack Dennis and his students at MIT, marking it as a concept developed remarkably early in the history of computing.

Contrasting Dataflow with Traditional Control Flow Programming

To understand the significance and novelty of dataflow programming, it's crucial to compare it with the more conventional programming approach, often referred to as control flow, procedural, or imperative programming.

Control Flow Programming: Commands in Sequence

Traditional programming, aligned with the von Neumann architecture, views a program as a series of commands executed in a specific order. Think of it like a recipe: you follow the steps one after another, and the order is critical. This is sequential in nature, meaning operations are performed one after the other.

Control Flow Programming: A programming paradigm where the program execution order is explicitly dictated by control structures (like loops, conditional statements, and function calls). The focus is on the sequence of commands to be executed.

In this model, data is often considered "at rest," residing in memory locations until it's acted upon by instructions. The program dictates when and how data is processed. Languages like C, Java, and Python are predominantly control flow languages, although they may incorporate functional aspects.

Analogy: Imagine a single chef (the processor) in a kitchen. The chef follows a recipe (the program) step-by-step, retrieving ingredients (data) as needed, performing operations (cooking steps), and producing the final dish.

Dataflow Programming: Data in Motion

In stark contrast, dataflow programming prioritizes the movement of data. Programs are visualized as networks of interconnected operations, where data flows between these operations like a current through a circuit.

Dataflow Programming: Emphasizes the flow of data as the driving force of computation. Operations are triggered by the availability of input data, and results are passed on as output data.

Operations in a dataflow program are like "black boxes" with clearly defined inputs and outputs. An operation only executes when all its required input data becomes available. This data-driven execution model naturally lends itself to parallelism. Because operations are only dependent on data availability, many operations can potentially execute concurrently if the necessary data is ready. This inherent parallelism makes dataflow programs well-suited for large, distributed systems.

Analogy: Think of an assembly line in a factory. Each station (operation) performs a specific task on the product (data) as it moves along the line. Stations work independently and concurrently, triggered by the arrival of the product at their station.

Key Concepts in Dataflow Programming

State Management

The concept of state in programming refers to the current condition of a system, a snapshot of its variables and memory at a particular point in time. Traditional programs often rely heavily on mutable state, where variables can be changed throughout the program's execution. This state can be complex and often implicitly managed by the program, making it challenging to track, especially in parallel environments.

State (in Programming): The condition of a program at a specific point in time, encompassing the values of variables, memory, and other relevant data. In mutable state systems, this condition can change throughout the program's execution.

In control flow programming, managing shared state across multiple processors in parallel systems can become a significant bottleneck. Programmers often have to add extra code to explicitly manage and synchronize state, which can be complex, error-prone, and negatively impact performance. This complexity has been cited as a contributing factor to the performance challenges of technologies like Enterprise Java Beans in data-intensive, non-transactional applications.

Dataflow programming elegantly addresses the state problem. Since operations are triggered by data availability and produce outputs, they are inherently stateless. They don't need to remember past computations or maintain internal variables across executions. This stateless nature simplifies parallel execution because there's no shared mutable state to manage or synchronize.

In the assembly line analogy, each worker (operation) only needs to know about the materials (data) arriving at their station. They don't need to keep track of the overall state of the factory.

Representation of Dataflow Programs

Traditional programs are typically represented as text-based instructions in a sequential order. This is suitable for describing serial processes where data is piped between small, single-purpose tools.

Dataflow programs, however, often benefit from a different representation that emphasizes the flow of data.

• Visual Representation: Dataflow programs are frequently visualized as graphs or diagrams. Nodes in the graph represent operations (or "actors"), and edges represent the data flow connections between them. This visual approach makes the data dependencies and program structure explicit and intuitive.
• Textual Representation: While visual representations are common, dataflow programs can also be expressed textually. Languages like SISAL and SAC resemble traditional languages in syntax but enforce single assignment principles that facilitate dataflow execution.
• Internal Representation: At a lower level, a dataflow program might be implemented using data structures like hash tables. Inputs can be keys, and values can be pointers to instructions or operations. When an operation completes and produces output, the system checks for operations whose inputs are now valid and ready for execution.

This representation focuses on what data is transformed and how it flows, rather than when each operation is executed, which is a key shift from control flow.

Incremental Updates and Efficiency

Modern dataflow systems are further enhanced by techniques like incremental computing.

Incremental Computing: A computation approach that aims to update the result of a computation when the input data changes, rather than recomputing everything from scratch. It leverages previous computations to efficiently process updates.

Libraries like Differential Dataflow and Timely Dataflow employ incremental computing to achieve significantly improved efficiency, especially when dealing with large datasets or continuous data streams where changes are frequent but small relative to the overall data volume. This allows dataflow programs to be highly responsive and efficient in dynamic environments.

History and Evolution: An Idea Before Its Time?

Dataflow programming's roots extend back to the early days of computing, showcasing its visionary nature.

• BLODI (1961): One of the earliest dataflow languages, BLock DIagram (BLODI), was developed at Bell Labs for specifying sampled data systems, like those used in signal processing. It allowed users to describe systems graphically using functional blocks (amplifiers, adders, delays) and their interconnections. BLODI specifications were compiled into a single loop that simulated the system's behavior over time.

• Bert Sutherland's Graphical Dataflow (1966): Bert Sutherland's Ph.D. thesis introduced a graphical dataflow programming framework aimed at simplifying parallel programming. This early work demonstrated the potential of visual dataflow for making parallelism more accessible.

• Supercomputer Era Languages: Many dataflow languages emerged from supercomputer labs, driven by the need for parallelism in high-performance computing.

  • POGOL (NSA): This language, developed at the NSA, was used for large-scale data processing applications. It optimized file-to-file operations, eliminating the need for intermediate files, thus enhancing efficiency.
  • SISAL (Lawrence Livermore National Laboratory): Streams and Iteration in a Single Assignment Language (SISAL) was a popular dataflow language that, despite resembling traditional statement-based languages, enforced the principle of single assignment (variables assigned only once). This made data dependencies explicit and simplified compiler optimizations for parallel execution. SAC (Single Assignment C) is an offshoot that aimed to bring dataflow principles closer to the widely used C language.

• Signal Processing and Embedded Systems: The U.S. Navy funded the development of SPGN (Signal Processing Graph Notation) and ACOS in the early 1980s for signal processing applications. These are still used in various field platforms today, highlighting the enduring relevance of dataflow in specific domains.

• Prograph (Graphical Programming): Prograph, originally developed for the Macintosh, took a radical approach by completely replacing variables with visual connections (lines) between inputs and outputs in a graphical programming environment. It was a purely visual dataflow language, emphasizing the graphical representation.

• Hardware Architectures: Recognizing the potential of dataflow, architectures like MIT's tagged token dataflow architecture (designed by Greg Papadopoulos) were developed to efficiently execute dataflow programs in hardware.

• Dataflow for Distributed Systems: Dataflow concepts have also been proposed for managing complexity in distributed systems. The live distributed objects programming model uses data flows to represent and manage state and communication in distributed components, akin to how variables and parameters work in languages like Java.

Why Ahead of Its Time?

Dataflow programming emerged in an era when sequential, von Neumann architectures and imperative programming dominated. While the concept of parallelism was understood, mainstream hardware and software tools were not readily available to fully exploit the inherent parallelism of dataflow. Compilers and runtime environments were not as sophisticated in automatically parallelizing code. As a result, dataflow programming remained largely in research and specialized domains, failing to achieve widespread adoption in general-purpose programming.

However, the core ideas of dataflow – explicit data dependencies, inherent parallelism, and simplified state management – are increasingly relevant in today's computing landscape characterized by multi-core processors, distributed systems, and massive datasets.

Dataflow Programming Languages and Libraries

The following is a list of dataflow programming languages and libraries, illustrating the breadth and diversity of implementations:

Languages

• Céu: A reactive programming language with dataflow aspects.
• ASCET: Primarily used in automotive embedded systems development, often employing dataflow principles for modeling and simulation.
• AviSynth: A scripting language for video processing, using a dataflow approach for video filtering and manipulation.
• BMDFM Binary Modular Dataflow Machine: A dataflow language and architecture.
• CAL: A dataflow language focused on multimedia and stream processing.
• Cuneiform: A functional workflow language based on dataflow principles.
• CMS Pipelines: A dataflow-oriented pipeline processing system, often used in IBM mainframe environments.
• Hume: A functional programming language with strong dataflow features.
• Joule: A dataflow language for concurrent programming.
• Keysight VEE (Visual Engineering Environment): A graphical dataflow language for measurement and automation.
• KNIME (Konstanz Information Miner): A visual dataflow platform for data analytics, reporting, and integration.
• LabVIEW (Laboratory Virtual Instrument Engineering Workbench), G: A widely used graphical dataflow language for instrumentation, measurement, and control systems.
• Linda: A coordination language that can be used to implement dataflow systems.
• Lucid: An early dataflow programming language, known for its mathematical foundations.
• Lustre: A synchronous dataflow language for safety-critical reactive systems.
• Max/MSP: A visual programming language for music and multimedia, based on dataflow principles.
• Microsoft Visual Programming Language (Microsoft Robotics Studio): A visual dataflow environment for robotics programming.
• Nextflow: A workflow language for data-intensive computational pipelines, often used in bioinformatics.
• Orange: An open-source visual programming tool for data mining, statistical analysis, and machine learning.
• Oz: A multi-paradigm language that includes dataflow concurrency features.
• Pipeline Pilot: A commercial dataflow platform for scientific data analysis and workflow automation.
• Prograph: A visual dataflow language as discussed earlier.
• Pure Data (Pd): An open-source visual programming language for real-time interactive multimedia works, similar to Max/MSP.
• Quartz Composer: A visual programming tool by Apple for graphic animations and effects, utilizing dataflow principles.
• SAC (Single Assignment C): As mentioned, a dataflow-oriented variant of C.
• SIGNAL: A synchronous dataflow language for multi-clock system specifications.
• Simulink: A block diagram environment for simulation and model-based design, often used in engineering and control systems, based on dataflow concepts.
• SISAL: The pioneering dataflow language from Lawrence Livermore National Laboratory.
• SystemVerilog: A hardware description language with dataflow modeling capabilities.
• Verilog: Another hardware description language, now part of SystemVerilog, also supporting dataflow descriptions.
• VisSim: A block diagram language for dynamic system simulation and firmware generation.
• VHDL: A hardware description language with dataflow features.
• Wapice IOT-TICKET: A visual dataflow programming language for IoT data analysis and reporting.
• XEE (Starlight) XML engineering environment: A dataflow-based environment for XML processing.
• XProc: An XML pipeline language based on dataflow principles.

Libraries

• Apache Beam: A Java/Scala SDK for unified stream and batch data processing, supporting dataflow execution engines like Apache Spark, Apache Flink, and Google Dataflow.
• Apache Flink: A Java/Scala library and framework for stream and batch processing, capable of running on distributed clusters.
• Apache Spark: While primarily known for its distributed data processing capabilities, Spark also incorporates dataflow principles in its execution model.
• SystemC: A C++ library for system-level design, particularly in hardware, often used with dataflow modeling.
• TensorFlow: A widely used machine learning library that leverages dataflow programming for defining and executing computational graphs.

Use Cases and Applications

Dataflow programming is particularly well-suited for applications with inherent parallelism and where managing data dependencies is crucial. Some key areas include:

• Signal Processing: As seen in BLODI, SPGN, and ACOS, dataflow is a natural fit for signal processing applications where data streams are processed by a series of operations (filters, transforms, etc.).
• Multimedia Processing: Languages like AviSynth, Max/MSP, Pure Data, and Quartz Composer demonstrate the effectiveness of dataflow in video, audio, and graphics processing, where pipelines of operations are common.
• Scientific Computing and Data Analysis: Languages like SISAL and platforms like KNIME and Pipeline Pilot are used in scientific and data-intensive computing for tasks like simulation, data mining, and workflow automation.
• Hardware Design: Hardware description languages like SystemVerilog, Verilog, and VHDL utilize dataflow concepts to model the behavior of digital circuits.
• Embedded Systems: ASCET and Simulink exemplify the use of dataflow in modeling and developing embedded systems, especially in domains like automotive and control engineering.
• Data Streaming and Real-time Analytics: Libraries like Apache Beam and Apache Flink and workflow languages like Nextflow are designed for processing continuous data streams and building real-time analytical pipelines.
• Machine Learning: TensorFlow's use of dataflow graphs for defining and executing machine learning models underscores the paradigm's applicability in complex computational tasks.
• Internet of Things (IoT): Wapice IOT-TICKET demonstrates the application of visual dataflow programming for IoT data analysis and reporting.

Why Dataflow's Time is Now: Resurgence and Relevance

Although conceived decades ago, dataflow programming is experiencing a resurgence in interest and relevance due to several converging trends in modern computing:

• Rise of Multi-core Processors and Parallel Computing: The widespread availability of multi-core processors and distributed computing environments makes the inherent parallelism of dataflow a significant advantage. Dataflow programs can naturally exploit these architectures without requiring complex manual parallelization.
• Big Data and Data Streaming: The explosion of data and the need to process massive datasets and continuous data streams in real-time perfectly align with dataflow's strengths in handling data-driven computations and streaming data.
• Complexity of Modern Software Systems: As software systems become increasingly complex and distributed, the explicit data dependency representation and simplified state management offered by dataflow programming become valuable for managing complexity and improving maintainability.
• Visual Programming and Domain-Specific Languages: The visual nature of dataflow programming is appealing for domain experts who may not be traditional programmers. Visual dataflow tools and domain-specific languages are making dataflow more accessible and applicable in diverse fields.

Dataflow programming, initially a "lost innovation" due to limitations in its time, is now finding its footing as a powerful and relevant paradigm for addressing the challenges of modern computing. Its ability to naturally express parallelism, manage state effectively, and handle data-driven computations makes it a valuable approach for a wide range of applications, from high-performance computing to real-time data analytics and beyond.

Conclusion

Dataflow programming represents a paradigm shift from control-centric to data-centric thinking in programming. By focusing on the flow of data and the dependencies between operations, it offers a powerful and intuitive approach to building concurrent, efficient, and maintainable systems. While initially ahead of its time, dataflow programming's core principles are now more relevant than ever in the era of parallel computing, big data, and complex software systems. As hardware and software continue to evolve, dataflow programming is poised to play an increasingly important role in shaping the future of computation.